package mess;

public class LeeCode_53 {
    public static void main(String[] args) {
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
//        System.out.println(maxSubArray(nums));
        System.out.println(maxSubArray(new int[]{3,-3,2,-3}));
    }
    private static int maxSubArray(int[] nums) {
        int start = -1;
        int max = nums[0];
        int sum = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            //没有start位置
            if (start < 0){
                //找到start位置
                if (num > 0){
                    start = i;
                    sum = num;
                    max = Math.max(max, num);
                    continue;
                }else
                    max = Math.max(max, num);
            }
            //已有start位置
            if (start >= 0){
                sum += num;
                if (sum > 0)
                    max = Math.max(max, sum);
                else {
                    start = -1;
                }
            }
        }
        return max;
    }
}
